#include <iostream>
#include <fstream>
#include <string>

using namespace std;

#define MAXARRAY 10000
#define INPUTFILE "QuickSort.txt"

void init(int *intarray);
void swap(int *a, int *b);
int quickSort(int * intarray,int length,int first, int last); //return number of comparison
int selectPivotFirst(int *intarray,int length, int first, int last); //select first element as pivot
int selectPivotLast(int *intarray,int length, int first, int last); //pivot last element
int selectPivotMid(int *intarray,int length, int first, int last); //pivot midian of first, last, middle
int partition(int * intarray,int length, int first, int last, int pivot); //do partition, return pivot index


int main(int argc, char argv[])
{
	int result;
	int integerarray[MAXARRAY];
	
	init(integerarray);

	result=quickSort(integerarray, MAXARRAY, 0, MAXARRAY-1);

	cout<<result<<endl;

	system("pause");

	return result;

}



void init(int *intarray)
{
	string buffer;
	ifstream f(INPUTFILE,ios::in);
	
	if(f.is_open()){
			for (int i=0;i<MAXARRAY;i++){
				getline(f,buffer);
				intarray[i]=atoi(buffer.c_str());
			}
	}
	else cout<<"cannot open file";
	f.close();
}

void swap(int *a, int *b)
{
	int temp;
	temp=*b;
	*b=*a;
	*a=temp;
}

int quickSort(int *intarray,int length, int first, int last)
{
	int pivotindex=0,result=0, lengthLeft,lengthRight;


	if (length==1) return 0;
	else if(length==2) {
		if(intarray[first]>intarray[last]) swap(&intarray[first],&intarray[last]);
		return 1;
	}
	
	pivotindex=selectPivotFirst(intarray,length,first,last);

	pivotindex=partition(intarray,length,first,last,pivotindex);

	lengthLeft=pivotindex-first;
	lengthRight=last-pivotindex;
	
	if( lengthLeft==0) //all element is greater than pivot
	{
		result=lengthRight-1;
		result+=quickSort(intarray,lengthRight,pivotindex+1,last);
	}else if(lengthRight==0) // all element is smaller than pivot
	{
		result=lengthLeft-1;
		result+=quickSort(intarray,lengthLeft,first,pivotindex-1);
	}else
	{
		result=lengthLeft+lengthRight-2;
		result+=quickSort(intarray,lengthLeft,first,pivotindex-1);
		result+=quickSort(intarray,lengthRight,pivotindex+1,last);
	}

	return result;
}

int selectPivotFirst(int *intarray, int length, int first, int last)
{
	return first;
}
int selectPivotLast(int *intarray, int length, int first, int last)
{
	return last;
}

int selectPivotMid(int *intarray, int length, int first, int last)
{
	int middle=(first+last)/2,temp=intarray[first],pivot=first;
	if (temp<intarray[middle])
	{
		temp=intarray[middle];
		pivot=middle;
	}
	if(temp<intarray[last])
	{
		pivot=last;
	}

	return pivot;
}

int partition(int * intarray,int length, int first, int last, int pivot)
{
	int i=first+1,j=first+1,p=intarray[pivot];
	
	swap(&intarray[first],&intarray[pivot]);
	while(j<=last)
	{
		if(p>intarray[j])
		{
			swap(&intarray[i],&intarray[j]);
			i++;
		}
		j++;

	}

	swap(&intarray[i-1],&intarray[first]);
	
	return i-1;
}